package algorithm.leetcode.I101to200;

import java.util.Arrays;

/**
 *
 */

public class Q132 {

    public int minCut(String s) {
        boolean[][] isHuiWen = new boolean[s.length()][s.length()];
        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j) isHuiWen[i][j] = true;
                else if (j - i == 1) isHuiWen[i][j] = s.charAt(i) == s.charAt(j);
                else isHuiWen[i][j] = s.charAt(i) == s.charAt(j) && isHuiWen[i+1][j-1];
            }
        }
        // dp数组含义:dp[k]表示第k个字符结尾的子串的最小切分次数,dp[0]=0
        int[] dp = new int[s.length()];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 0; i < s.length(); i++) {
            if (i == 0) dp[i] = 0;
            else {
                for (int j = 0; j <= i; j++) {
                    if (isHuiWen[j][i] && j == 0) dp[i] = 0;
                    // 当且仅当dp[j]可切分为几个小回文串,并且后一半是回文
                    else if (isHuiWen[j][i] && dp[j-1] != Integer.MAX_VALUE) dp[i] = Math.min(dp[i], dp[j-1] + 1);
                }
            }
        }
        return dp[s.length()-1];
    }

    public static void main(String[] args) {
        Q132 q132 = new Q132();
        System.out.println(q132.minCut("aab"));
    }

}
